package com.apkcore.bl;

import java.util.ArrayList;
import java.util.List;

/**
 * https://leetcode-cn.com/problems/binary-watch/submissions/
 */
public class _401二进制手表 {
    // 二进制01表示法
    // 小时0-11，4个bit
    // 分钟0-59 6个bit
    // 二进制中1的各就是turnedOn

    public List<String> readBinaryWatch3(int turnedOn) {
        List<String> ans = new ArrayList<String>();
        for (int h = 0; h < 12; ++h) {
            for (int m = 0; m < 60; ++m) {
                if (Integer.bitCount(h) + Integer.bitCount(m) == turnedOn) {
                    ans.add(h + ":" + (m < 10 ? "0" : "") + m);
                }
            }
        }
        return ans;
    }

    //  2^{10}=1024 种灯的开闭组合，即用一个二进制数表示灯的开闭，其高 4 位为小时，低 6 位为分钟
    // 本质上和readBinaryWatch3是一样的
    public List<String> readBinaryWatch2(int turnedOn) {
        List<String> ans = new ArrayList<String>();
        for (int i = 0; i < 1024; ++i) {
            int h = i >> 6, m = i & 63; // 用位运算取出高 4 位和低 6 位
            if (h < 12 && m < 60 && Integer.bitCount(i) == turnedOn) {
                ans.add(h + ":" + (m < 10 ? "0" : "") + m);
            }
        }
        return ans;
    }

    // 这种排列组合理所当然想到
    // dfs回溯
    List<String> ans = new ArrayList<>();
    int[] a = new int[]{1, 2, 4, 8, 1, 2, 4, 8, 16, 32};

    public List<String> readBinaryWatch1(int num) {
        dfs(num, 0, 0, 0);
        return ans;
    }

    private void dfs(int cnt, int h, int m, int idx) {
        if (cnt == 0) {
            ans.add(h + ":" + (m > 9 ? m : "0" + m));
            return;
        }
        for (int i = idx; i < a.length; i++) {
            // 小时
            if (i < 4 && h + a[i] < 12) {
                dfs(cnt - 1, h + a[i], m, i + 1);
            }
            // 分钟
            if (i >= 4 && m + a[i] < 60) {
                dfs(cnt - 1, h, m + a[i], i + 1);
            }
        }
    }

    //
    // 直接把二进制的问题转换为数组累加问题
    int[] hours = new int[]{1, 2, 4, 8, 0, 0, 0, 0, 0, 0};
    int[] minutes = new int[]{0, 0, 0, 0, 1, 2, 4, 8, 16, 32};
    List<String> res = new ArrayList<>();

    public List<String> readBinaryWatch(int turnedOn) {
        // 方法二：采用回溯法
        backTrack(turnedOn, 0, 0, 0);
        return res;
    }


    // 回溯的参数：num(需要点亮的灯，初始为turnedOn),index(点亮的下标)
    // hour(小时数)minute(分钟数)
    public void backTrack(int num, int index, int hour, int minute) {
        // 剪枝操作
        if (hour > 11 || minute > 59) {
            return;
        }
        // 递归出口,当点亮到第0栈灯的时候，那么回溯所有数据
        if (num == 0) {
            // 进行字符串拼接
            StringBuilder sb = new StringBuilder();
            sb.append(hour).append(':');
            if (minute < 10) {
                sb.append('0');
            }
            sb.append(minute);
            res.add(sb.toString());
            //记得return终止掉
            return;
        }
        // 这里是从下标开始递归遍历
        for (int i = index; i < 10; i++) {
            backTrack(num - 1, i + 1, hour + hours[i], minute + minutes[i]);
        }
    }


    // 打表
    //可以穷举
    //0个1；1个1；2个1；3个1
    String[][] hour = {{"0"}, {"1", "2", "4", "8"}, {"3", "5", "6", "9", "10"}, {"7", "11"}};
    //0个1；1个1；2个1；3个1，4个1；5个1
    String[][] minute = {{"00"}, {"01", "02", "04", "08", "16", "32"},
            {"03", "05", "06", "09", "10", "12", "17", "18", "20", "24", "33", "34", "36", "40", "48"},
            {"07", "11", "13", "14", "19", "21", "22", "25", "26", "28", "35", "37", "38", "41", "42", "44", "49", "50", "52", "56"},
            {"15", "23", "27", "29", "30", "39", "43", "45", "46", "51", "53", "54", "57", "58"},
            {"31", "47", "55", "59"}};

    public List<String> readBinaryWatch5(int num) {
        List<String> ret = new ArrayList();
        if (num > 8) return ret;

        for (int i = 0; i <= 3 && i <= num; i++) {
            if (num - i <= 5) {
                for (String str1 : hour[i]) {
                    for (String str2 : minute[num - i]) {
                        ret.add(str1 + ":" + str2);
                    }
                }
            }
        }
        return ret;
    }

    
}
